package hot_problems_100;

import java.util.*;

public class P6_0015 {
    /*
    * 给你一个整数数组 nums ，判断是否存在三元组
    * [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，
    * 同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
    * 注意：答案中不可以包含重复的三元组。
    *
    * 3 <= nums.length <= 3000
    * -1e5 <= nums[i] <= 1e5
    * */


    // 单指针 + 二分查找 O (n^2 log n )

    private int binarySearch(int[] nums, int left, int right, int target){
        while(right >= left){
            int mid = (left + right) / 2;
            if(nums[mid]==target) return mid;
            else if(nums[mid] > target) right = mid -1;
            else {
                left = mid + 1;
            }
        }
        return -1;
    }


    public List<List<Integer>> threeSum_old(int[] nums){
        Arrays.sort(nums);
        Set<List<Integer>> res = new HashSet<>();
        for(int k=nums.length-1; k>=2; k--){
            int sum = - nums[k];
            for(int i=0; i<k-1; i++){
                int j = binarySearch(nums, i+1, k-1, sum-nums[i]);
                if(j<0) continue;
                List<Integer> list = new ArrayList<>();
                list.add(nums[i]);
                list.add(nums[j]);
                list.add(nums[k]);
                res.add(list);


                if(nums[i] > sum / 2) break;
            }
        }
        return res.stream().toList();
    }

    // 双指针： O (n^2)

    public List<List<Integer>> threeSum(int[] nums){
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        for(int k=nums.length-1; k>=2; k--){
            if(k<nums.length-1 && nums[k]==nums[k+1]) continue;
            int i=0, j=k-1;
            while(i<j){
                if(nums[i] + nums[j] == -nums[k]){
                    res.add(Arrays.asList(nums[i], nums[j], nums[k]));
                    while(i<j && nums[i] == nums[i+1]) i++;
                    while(i<j && nums[j] == nums[j-1]) j--;
                    i++;
                    j--;
                } else if(nums[i] + nums[j] > -nums[k]){
                    j--;
                } else {
                    i++;
                }
            }
        }
        return res;
    }

    public static void main(String[] args){
        P6_0015 p = new P6_0015();
        int[] nums = {-1,0,1,2,-1,-4};
        List<List<Integer>> res = p.threeSum(nums);
        for(List<Integer> list : res){
            System.out.print("[ ");
            for(int i: list){
                System.out.print(i+", ");
            }
            System.out.println(" ]\n");
        }
    }
}
